package com.haidechizi.sort;

import java.util.Arrays;

/**
 * @author: wangdejun
 * @create: 2020-03-14 10:44
 **/
public class MergeSort {

    public static void main(String[] args) {
        int[] arr = new int[]{2, 3, 5, 0, 1, 4, 6, 7};
//        merge(arr, 0, 2, arr.length - 1);
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));

    }

    public static void mergeSort(int[] arr, int low, int high) {
        // 结束递归的条件
        if (low >= high) {
            return;
        }
        // 获取数组的中间
        int middle = (low + high) / 2;
        // 对左侧的数进行递归归并排序
        mergeSort(arr, low, middle);
        // 对右侧的数进行递归归并排序
        mergeSort(arr, middle + 1, high);
        // 合并两侧已经排好序的数组
        merge(arr, low, middle, high);
    }


    /**
     * 合并函数
     * 将两个排序好的数组合并成一个数组
     *
     * @param arr
     * @param start
     * @param middle
     * @param end
     */
    public static void merge(int[] arr, int start, int middle, int end) {
        // 虎丘临时数组的长度
        int length = end - start + 1;
        // 定义临时数组，用于存放合并后的数组
        int[] temp = new int[length];

        int low = start;
        int high = middle + 1;
        // 当两个数组中都有元素时，进行循环
        int index = 0;
        while (low <= middle && high <= end) {
            // 低位数小于高位的数
            while (low <= middle && arr[low] <= arr[high]) {
                temp[index] = arr[low];
                index++;
                low++;
            }
            while (high <= end && arr[low] >= arr[high]) {
                temp[index] = arr[high];
                index++;
                high++;
            }
        }
        // 当第一个数组的数部位空时，将第一个数组的数放入到临时数组中
        while (low <= middle) {
            temp[index] = arr[low];
            index++;
            low++;
        }
//       当第二个数组的数不为空时，将第二个数组的数放入到临时数组中
        while (high <= end) {
            temp[index] = arr[high];
            index++;
            high++;
        }
        // 将临时数组中的数放入到原数组中
        for (int i = 0; i < temp.length; i++) {
            arr[start + i] = temp[i];
        }

    }

}
